public class Wu_5_13 {
    public static void main(String[] args) {
        int [] prices=new int[]
                {100,133,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};
        // call profit_change
        int[] profits=new Wu_5_13().profit_change(prices);
        for(int i:profits)
            System.out.print(i+" ");
        System.out.println();

        // call FindMax
        Ret ret=new Wu_5_13().FindMax(profits,0, profits.length-1);
        System.out.println(ret);

        // call maxProfit
        Ret ret1=new Wu_5_13().maxProfit(prices);
        System.out.println(ret1);

        // call maxProfit_kTrade
        int ret2=new Wu_5_13().maxProfit_kTrade(prices,2);
        System.out.println(ret2);
    }
    // k trades are allowed ,the max profit
    int maxProfit_kTrade(int[] prices,int k){
        if(prices.length <= 1) return 0;
        int [][] dp=new int[k+1][prices.length]; // k+1 is for broad applicability
        for(int i=1;i<k+1;i++){
            int tmpMax=dp[i-1][0]-prices[0]; // the point of purchasing
            for(int j=1;j<prices.length;j++){
                dp[i][j]=Math.max(dp[i][j-1],prices[j]+tmpMax); // dynamic programming
                tmpMax=Math.max(tmpMax,dp[i-1][j-1]-prices[j]); // update tmpMax
            }
        }
        return dp[k][prices.length-1];
    }

    Ret maxProfit(int[] prices){
       if(prices.length<=1) return new Ret(0,0,0);

       int[] dp=new int[prices.length];
       dp[0]=0;
       int minPrice=prices[0]; // initial min price
       int left=0,right=0;
       int min_limit=0;

       for(int i=1;i<prices.length;i++) {
           if (prices[i] < minPrice) {
               minPrice = prices[i];//update the min price
               min_limit=i; //record the position of minPrice
           }
           dp[i]=Math.max(dp[i-1],prices[i]-minPrice);
           // update  | dp[i]=dp[i-1] not update
           if(dp[i]==prices[i]-minPrice){
               right=i;
               left=min_limit+1; // +1 maximum subArray
               // no +1 maxProfit
           }
       }
       return  new Ret(dp[prices.length-1],left,right);
    }

    // profit_change is defined for changing prices array into profits array

    int[] profit_change(int [] prices){
        int[] profits =new int[prices.length];
        profits[0]=0;
        for(int i=1;i<prices.length;i++){
            profits[i]=prices[i]-prices[i-1];
        }
        return profits;
    }

    //FindMax can't merge array,but Find_Mid_max can merge
    //define FindMax
    Ret FindMax(int [] profits,int low,int high){
        Ret ret;
        if (high == low) return new Ret(profits[low],low,high);

        int mid = (low + high) / 2;
        //left
        Ret left = FindMax(profits, low, mid);
        //middle
        Ret middle = Find_Mid_Max(profits, low, mid, high);
        //right
        Ret right = FindMax(profits, mid + 1, high);

        if (left.profit >= middle.profit && left.profit >= right.profit) {
            ret= left;
        } else if (middle.profit >= left.profit && middle.profit >= right.profit) {
            ret= middle;
        } else {
            ret= right;
        }
        return ret;
    }
    //define Find_Mid_Max
    Ret Find_Mid_Max(int [] profits,int low,int mid,int high){

        //left
        int sum=0;
        int max_left=mid; //record initial limits
        int left_sum=Integer.MIN_VALUE;
        for(int i=mid;i>=low;i--){
            sum+=profits[i];
            if(sum>left_sum){
                left_sum=sum; //left_sum is used to record the previous sum
                max_left=i; //update the left limit ; no -1  maximum subArray
                //max_left=i-1;  -i  maximum profit
            }
        }
        // right
        sum=0;
        int max_right=mid;
        int right_sum=Integer.MIN_VALUE;
        for(int i=mid+1;i<=high;i++){
            sum+=profits[i];
            if(sum>right_sum){
                right_sum=sum;
                max_right=i;
            }
        }
        return new Ret(left_sum+right_sum,max_left,max_right);
    }
}
class Ret{
    int low;
    int high;
    int profit;
    public Ret(int profit,int low,int high){
        this.low=low;
        this.high=high;
        this.profit=profit;
    }
    public String toString(){
        return "{"+profit + ","+low +","+high+"}";
    }
}
